package GBP;

import java.util.*;

/*
 * Evolution.java
 * Created: 2005-12-14 20:20
 */
/**
 * This class contains methods for evolution:
 *  - Selection
 *  - Mutation/Recombination
 *  - Replacement
 *
 * @author T.S.Yo
**/

public class Evolution{

// Constructor    
//    public Evolution(){}
    /** Evolving the GBP solutions **/
    public void evolveGBP(final Individual[] pop){
        // Random selection
        Individual[] parents = randSelection(pop);
        // Generate off-spring via uniform crossover
        Individual offspring = new Individual(parents[0]);
        offspring.setGenes(uniformCrossover(parents[0], parents[1]));
        // Replace the worst case in the old population
        replaceWorst(offspring, pop);
    }
    
// Selection
    /** Randomly Select 2 parents from the given population **/
    public Individual[] randSelection(final Individual[] pop){
        // Generate 2 random index numbers from given population
        Random rand = new Random();
        int pSize = pop.length;
        int indIndex1 = rand.nextInt(pSize);
        int indIndex2 = rand.nextInt(pSize);
        while(indIndex2 == indIndex1){
            indIndex2 = rand.nextInt(pSize);
        }
        //System.out.println("Randomly selected parents: " + indIndex1+"    "+indIndex2);    // For testing
        
        // Copy selected individuals as parents
        Individual[] parents = new Individual[2];
        parents[0] = new Individual(pop[indIndex1]);
        parents[1] = new Individual(pop[indIndex2]);
        //System.out.println("Parent 1: " + parents[0]);    // For testing
        //System.out.println("Parent 2: " + parents[1]);    // For testing
        return parents;
    }

// Recombination
   /** Uniformcrossover **/
    public int[] uniformCrossover(final Individual ind1, final Individual ind2)
    {
        int genoSize = ind1.getArraySize();     // Size of the genes
        int[] newGenes = new int[genoSize];     // new genes to return
        LinkedList<Integer> mismatch = new LinkedList<Integer>();
        
        // Check hamming distance: For GBP, 0011 and 1100 represent the same partitioning
        checkHamming(ind1, ind2);
        
        // Check exception
        if(genoSize!=ind2.getArraySize()){
            System.out.println("Parents with different length, return a random Individual");
        } else {    
            //System.out.println("Uniform Crossover");    // For testing
            // Recording mismatched positions
            for (int i = 0; i < genoSize; i++){
                if(ind1.getGenes()[i]==ind2.getGenes()[i]){
                    newGenes[i] = ind1.getGenes()[i];
                } else {
                    //System.out.println("    Mismatched position: "+i);    // For testing
                    newGenes[i] = -1;
                    mismatch.add(i);
                }
            }
            // Randomly assign half 0's and half 1's to mismatched positions
            int[] m = new int[mismatch.size()];
            for (int i = 0; i < (mismatch.size()); i++){
                m[i] = mismatch.get(i);
            }
            randPermute(m);
            //showArray(m);    // For testing
            for (int i = 0; i < (m.length/2); i++){
                newGenes[m[i]] = 0;
            }
            for (int i = (m.length/2); i < m.length; i++){
                 newGenes[m[i]] = 1;
            }
        }
        //showArray(newGenes);    // For testing
        return newGenes;
    }
//// Replacement
   /** Replace the worst individual **/
    public void replaceWorst(final Individual ind, final Individual[] pop)
    {
        Arrays.sort(pop, pop[0]);
        pop[0] = new Individual(ind);
    }
// Generating new individuals    /** Mutating from given individual **/
    public Individual mutation(final int mutOpt, Individual ind){
        Individual mutInd = new Individual(ind);
        //
        //  Not used for GBP
        //
        return mutInd;
    }
//---------------------------------------------------------------------
// Miscellaneous sub-functions
    /** Copy an integer array by values **/ 
	private int [] copyArray( int [] source ) {
		int [] result = new int[ source.length ];
		for( int i = 0; i < result.length; i++ )
			result[ i ] = source[ i ];
		return result;
	}
    
    /** check hamming distance **/ 
	private void checkHamming(final Individual ind1, final Individual ind2) {
		int hammingDistance = 0;
        int[] a1 = copyArray(ind1.getGenes());
        int[] a2 = copyArray(ind2.getGenes());
		// Count difference
        for( int i = 0; i < a1.length; i++ ){
            if (a1[i] != a2[i]){
                hammingDistance ++;
            }
        }
		// If difference > (# of nodes/2), flip one
        if(hammingDistance>(a1.length/2)){
            //System.out.println("Parent 1: " + ind1);    // For testing
            //System.out.println("Parent 2: " + ind2);    // For testing
            //System.out.println("    Hamming Distance too large, flip one parent");  // For testing
            int[] newA = flipArray(a2);
            ind2.setGenes(newA);
            //System.out.println("Parent 1: " + ind1);    // For testing
            //System.out.println("Parent 2: " + ind2);    // For testing
        }
	}

    /** Reverse the values of a bit string **/ 
	private int [] flipArray( int [] source ) {
		int [] result = new int[ source.length ];
		for( int i = 0; i < result.length; i++ )
			result[ i ] = (-1 * source[ i ]) + 1;
		return result;
	}

    /** Perform random permutation on an integer array **/ 
	private void randPermute( int[] a ) {
        //System.out.println("    Start random permutation");    // For testing
        Random rand = new Random();
        for(int i = 0; i < (a.length-1); i++){
            // j = random number within [ i, arraySize ]
            int j = rand.nextInt((a.length-i)) + i;
            // Swapa[i] and a[j]
            //System.out.println("      Swap "+i+" and "+j);     // For testing
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    
    /** Show the gain-values **/
    public void showArray(int[] a){
        String output = "Array Values: \n";
        for(int i = 0; i < a.length; i++){
           output = output + " " + a[i];
           if((i%25)==24) output = output + "\n";
        }
        System.out.println(output);
    }
}
